import java.util.LinkedList;
import java.util.Queue;

/**
 * @author LKQ
 * @date 2021/12/25 9:22
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode t12 = new TreeNode(12), t8 = new TreeNode(8), t6 = new TreeNode(6)
                ,t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3, t12, t8), t7 = new TreeNode(7, t6, null),
                t9 = new TreeNode(9, null, t2);
        TreeNode t10 = new TreeNode(10, t3, null), t4 = new TreeNode(4, t7, t9);
        TreeNode root = new TreeNode(1, t10, t4);
        Solution solution = new Solution();
        solution.isEvenOddTree(root);
    }

    public boolean isEvenOddTree(TreeNode root) {

        // 利用层序遍历
        Queue<TreeNode> q1 = new LinkedList<>();
        LinkedList<Integer> q2 = new LinkedList<>();
        q1.offer(root);
        // 刚开始层下标
        int level = 0;
        boolean isEvenOdd = true;
        if (root.val % 2 != 1) {
            return false;
        }
        while (!q1.isEmpty()) {
            if (level % 2 == 1) {
                // 奇数下标层
                if (q2.size() == 1 && q2.getFirst() % 2 == 1) {
                    // 只有一个数
                    isEvenOdd = false;
                }
                for (int i = 0; i < q2.size()-1; i++) {
                    if (!((q2.get(i) > q2.get(i+1) && q2.get(i) % 2 == 0 && q2.get(i+1) % 2 == 0))) {
                        isEvenOdd = false;
                        break;
                    }
                }
            }else  {
                // 偶数下标层
                if (q2.size() == 1 && q2.getFirst() % 2 == 0) {
                    // 只有一个数
                    isEvenOdd = false;
                }
                for (int i = 0; i < q2.size()-1 ; i++) {
                    if (!((q2.get(i) < q2.get(i+1) && q2.get(i) % 2 == 1 && q2.get(i+1) % 2 == 1))) {
                        isEvenOdd = false;
                        break;
                    }
                }
            }
            if (!isEvenOdd) {
                // 只要在某一处不达标，那么就是直接返回false;
                return false;
            }
            q2.clear();
            int size = q1.size();
            while (size > 0 ) {
                TreeNode temp = q1.poll();
                if (temp.left != null) {
                    q1.offer(temp.left);
                    q2.offer(temp.left.val);
                }
                if (temp.right != null) {
                    q1.offer(temp.right);
                    q2.offer(temp.right.val);
                }
                size--;
            }
            level++;
        }
        return isEvenOdd;
    }
}
